Section: New Results

Minimum ratio cover of matrix columns by extreme rays of its induced cone

Given a matrix $S$ and a subset of columns $R$, we studied the problem of finding a cover of $R$ with extreme rays of the cone $ℱ=\{v\in {ℝ}^n\mid Sv=\mathbf{0},v\ge \mathbf{0}\}$, where an extreme ray $v$ covers a column $k$ if $v_k>0$ [34] . In order to measure how proportional a cover is, we introduced two different minimisation problems, namely the minimum global ratio cover (MGRC) and the minimum local ratio cover (MLRC) problems. In both cases, we applied the notion of the ratio of a vector $v$, which is given by $\frac{{max}_i{v}_i}{{min}_{j\mid v_j>0}{v}_j}$. These problems were originally motivated by a biological question on metabolic networks. This notion of ratio is also of interest in the field of exact linear programming, where current algorithms for scaling a matrix have a complexity that depends on the ratio of its elements. We showed that these two problems are NP-hard, even in the case in which $\left|R\right|=1$. We introduced a mixed integer programming formulation for the MGRC problem, which is solvable in polynomial time if all columns should be covered, and introduce a branch-and-cut algorithm for the MLRC problem. Finally, we presented computational experiments on data obtained from real metabolic networks.